package woshiheima13;

import java.util.Arrays;


/**
 * 快速排序的实现（选取一个头跟尾指针通过指针的位置的数跟基数进行比较）
 */
public class KuaiSuTest {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 7, 8, 9, 5, 1, 2, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int start, int end) {
        //当start<end才进行递归
        if (start < end) {
            //把数组中第0个元素作为标准数
            int startd = arr[start];
            //记录要排序的下标
            int low = start;
            int hight = end;
            ;
            //循环找比标准数大的数和比标准数小的数(右指针)
            while (low < hight) {
                //右边的数字比标准数大
                while (low < hight && startd<=arr[hight]) {
                    hight--;
                }
                //如果右边的数字比左边的小就替换
                arr[low] = arr[hight];


                //左边的数字比标准数小（左指针）
                while (low < hight && arr[low] <= startd) {
                    low++;
                }
                //如果左边的数比标准数大就替换掉右边的数
                arr[hight] = arr[low];
            }
            //当low=high把标准数赋值给低所在的位置元素
            arr[low]=startd;


            //左边的小数进行递归 low变成了标准数的位置
            quickSort(arr, start, low);
            //右边大数进行递归
            quickSort(arr, low + 1, end);

        }
    }
}